package com.ztom.top100;

/**
 * 最小覆盖子串
 * <p>
 * https://leetcode-cn.com/problems/minimum-window-substring/
 *
 * @author ZhangTao
 */
public class Code32MinWindow {

    public String minWindow(String s, String t) {
        if (s == null || t == null || s.length() < t.length()) {
            return "";
        }
        char[] str1 = s.toCharArray();
        char[] str2 = t.toCharArray();
        // 记录 t 中有哪些字符以及出现多少次
        int[] need = new int[128];
        for (char c : str2) {
            need[c]++;
        }
        // 记录 t 中字符出现总次数, 用于判断 t 是否完全被覆盖
        int tNeedCount = str2.length;

        // 记录最小子串左位置和长度
        int minL = 0;
        int min = Integer.MAX_VALUE;
        // 窗口遍历 s
        for (int l = 0, r = 0; r < str1.length; r++) {
            if (need[str1[r]] > 0) {
                // 当前字符是 t 中的字符
                tNeedCount--;
            }
            // 当前字符入窗口
            need[str1[r]]--;

            // 如果完全包含了 t
            if (tNeedCount == 0) {
                // 窗口左边界往右, 移除掉非 t 中字符, 直到遇上 t 中字符停止
                while (l < r && need[str1[l]] < 0) {
                    // 字符从窗口左边界出窗口
                    need[str1[l]]++;
                    l++;
                }
                // 如果产生了新的最小长度子串
                if (r - l + 1 < min) {
                    minL = l;
                    min = r - l + 1;
                }
                // 让 l 再增加一个位置, 开始寻找下一个满足条件的滑动窗口
                need[str1[l]]++;
                l++;
                tNeedCount++;
            }
        }

        return min == Integer.MAX_VALUE ? "" : s.substring(minL, minL + min);
    }
}
